\documentclass[12pt,a4paper]{article}
\usepackage{xeCJK}
\usepackage{ctex}
\usepackage{booktabs}
\usepackage{makecell}
\usepackage{geometry}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{graphicx}
\usepackage{wrapfig}
\usepackage{abstract}
\usepackage{float}
\usepackage{algorithmicx}
\usepackage[ruled]{algorithm}
\usepackage{algpseudocode}
\usepackage{xcolor}
\usepackage{setspace}
\usepackage{color}
\usepackage{bm}
\usepackage{url}
\usepackage{cite}
\usepackage{array}
\usepackage{textcomp}
\usepackage{appendix}
\usepackage{listings}

\setstretch{1.2} 
\setlength{\parindent}{0.8cm}
\geometry{left=3cm,right=3cm,top=2.5cm,bottom=2.5cm}
\title{\vspace{-2cm} \textbf{Theoretical Assignment 1 of Numerical Analysis}}

\author{赵竟廷 3200105665}
\date{September 2022}

\begin{document}
\maketitle

\section{Theoretical Questions \uppercase\expandafter{\romannumeral1}}

\begin{itemize}
    \item Here we think that "the interval \textbf{at} the $n$th step" means the interval in which the $n$th step occurs. Set $w_i$ as the width of the interval at the $i$th step ($w_1=3.5-1.5=2$, $i=1,2,\dots ,n$ ) then we have
    \begin{equation}
        w_n=\frac{w_1}{2^{n-1}}=\frac{1}{2^{n-2}}.
    \end{equation}
    \item Set $a$ to be the midpoint of the interval.From what we set above, we can know that the distance between $a$ and one of the endpoint of the interval is half of the width of the interval. Set $x$ as the maximum possible distance between the root $r$ and $a$, then we have 
    \begin{equation}
        x=\frac{w_n}{2}=\frac{1}{2^{n-1}}.
    \end{equation}
\end{itemize}

\section{Theoretical Questions \uppercase\expandafter{\romannumeral2}}

Let $x^*$ be the root, and $y_n$ be the midpoint of the interval after the $n$th step. Then we have 
\begin{equation}
    \epsilon \ge \frac{|x^*-y_n|}{x^*}.
\end{equation}
According to the information in question stem and the solution of theoretical questions 1, we know that $a_0 \leq x^* \leq b_0$, and $|x^*-y_n| \leq \frac{|a_0-b_0|}{2^{n+1}}$.

So, there should be 
\begin{equation}
    \frac{|x^*-y_n|}{x^*}\leq \frac{b_0-a_0}{2^{n+1}a_0}\leq \epsilon 
\end{equation}
\begin{equation}
    \frac{log(b_0-a_0)}{log2}\leq n+1+\frac{log \epsilon+log\,a_0}{log2}
\end{equation}
And after transposition we can prove that 
\begin{equation}
    n\ge \frac{log(b_0-a_0)-log\epsilon-log \,a_0}{log2}-1.
\end{equation}

\section{Theoretical Questions \uppercase\expandafter{\romannumeral3}}

The Newton's method can be expressed by the following formula:
\begin{equation}
    x_{n+1}=x_n-\frac{p(x_n)}{p'(x_n)}.
\end{equation}
Then by calculating, we can get the results which are showed in the following table.
\setlength{\tabcolsep}{10mm}{
\begin{table}[H]
\renewcommand{\arraystretch}{1.2}
 \centering
 \label{tab:pagenum}
 \setlength{\tabcolsep}{1.2cm}{

 \begin{tabular}{cccc}
  \toprule
  \multicolumn{1}{c}{$\bm{i}$}& \multicolumn{1}{c}{$\bm{x_i}$}& \multicolumn{1}{c}{$\bm{p(x_i)}$}& \multicolumn{1}{c}{$\bm{p'(x_i)}$}\\
  \midrule

  \multicolumn{1}{c}{$0$}&
  \multicolumn{1}{c}{$-1$}&
  \multicolumn{1}{c}{$-3$}&
  \multicolumn{1}{c}{$16$}\\
    \multicolumn{1}{c}{$1$}&
  \multicolumn{1}{c}{$-0.812500$}&
  \multicolumn{1}{c}{$-0.465820$}&
  \multicolumn{1}{c}{$11.171875$}\\
    \multicolumn{1}{c}{$2$}&
  \multicolumn{1}{c}{$-0.770804$}&
  \multicolumn{1}{c}{$-0.020138$}&
  \multicolumn{1}{c}{$10.212886$}\\
    \multicolumn{1}{c}{$3$}&
  \multicolumn{1}{c}{$-0.768832$}&
  \multicolumn{1}{c}{$-0.000043$}&
  \multicolumn{1}{c}{$10.168568$}\\
      \multicolumn{1}{c}{$4$}&
  \multicolumn{1}{c}{$-0.768828$}&
  \multicolumn{1}{c}{$-0.000000$}&
  \multicolumn{1}{c}{$10.168471$}\\

  \bottomrule
 \end{tabular}}
\end{table}
}

\section{Theoretical Questions \uppercase\expandafter{\romannumeral4}}

From the definition of the error of Newton's method, we know that $e_n=|x_n-x^*|$, $e_{n+1}=|x_{n+1}-x^*|$.
Then we have
\begin{equation}
    |x_{n+1}-x^*|=|x_n-x^*-\frac{f(x_n)}{f'(x_0)}|=
    \begin{cases}
        (x_n-x^*)-\frac{f(x_n)}{f'(x_0)}\quad ((x_n-x^*)\ge \frac{f(x_n)}{f'(x_0)})\\
        -(x_n-x^*)+\frac{f(x_n)}{f'(x_0)}\quad ((x_n-x^*)< \frac{f(x_n)}{f'(x_0)})\\
    \end{cases}.
\end{equation}
Suppose $x_{n+1}-x^*>0$ and $x_n-x^*\ge \frac{f(x_n)}{f'(x_0)}>0$,then we have
\begin{equation}
    e_{n+1}=e_n^s((x_n-x^*)^{1-s}-(x_n-x^*)^{-s}\frac{f(x_n)}{f'(x_0)})
\end{equation}
s can be any number except 0.Then we have
\begin{equation}
    \begin{cases}
        e_{n+1}=C e_n^s\\
        C=(x_n-x^*)^{1-s}-(x_n-x^*)^{-s}\frac{f(x_n)}{f'(x_0)}\\
    \end{cases}.
\end{equation}
Other situations of the problem can be similarly solved.

\section{Theoretical Questions \uppercase\expandafter{\romannumeral5}}

Suppose there is a function $f(x)=tan^{-1}x-x$, then we have
$f'(x)\leq 0$, and
\begin{equation}
    \begin{cases}
        f(x)<0 \quad \quad (x\in(0,\frac{\pi}{2}))\\
        f(x)=0 \quad \quad (x=0)\\
        f(x)>0 \quad \quad (x\in(-\frac{\pi}{2},0))\\
    \end{cases}
\end{equation}
\begin{itemize}
    \item If $x_0=0$, then $x_n=0$ is true for any $n$, thus the iteration converges.
    \item If $x_0\in (0,\frac{\pi}{2})$,then $f(x_n)=x_{n+1}-x_n<0$.
    So the sequence ($x_1,x_2,\dots,x_n,x_{n+1},\dots$) is monotonical. Since the sequence is bounded, according to the Monotone convergence theorem, the iteration converges in $(0,\frac{\pi}{2})$.
    \item If $x_0\in (-\frac{\pi}{2},0)$, then $f(x_n)=x_{n+1}-x_n>0$, the sequence is also monotonical and bounded. Then according to the Monotone convergence theorem, the iteration converges in $(-\frac{\pi}{2},0)$.
\end{itemize}
So, the iteration $x_{n+1}=tan^{-1}x_n$ converges.

\section{Theoretical Questions \uppercase\expandafter{\romannumeral6}}

Formulate x as a fixed point of the function $g(x)=\frac{1}{p+x}$.Then by calculating we can get the value of the continued fraction that:\quad $x=\frac{-p\pm \sqrt{p^2+4}}{2}$. Because $p>1$, we can know that $x>0$. So, the final value of the continued fraction is $x=\frac{-p+ \sqrt{p^2+4}}{2}$.

To prove that the result above is existent and meaningful, we should prove that the sequence of values converges. 

The sequence can be interpreted as $x=lim_{n\rightarrow \infty}x_n$,where $x_1=\frac{1}{p},x_2=\frac{1}{p+\frac{1}{p}},x_3=\frac{1}{p+\frac{1}{p+\frac{1}{p}}},\dots $.

${\forall}0<n<m,|m-n|<\delta$, we have
\begin{equation}
    |g(m)-g(n)|=|\frac{1}{m+p}-\frac{1}{n+p}|=|\frac{m-n}{(m+p)(n+p)}|<\delta
\end{equation}
Then according to theorem 1.38, we can know that  the sequence converges, thus it has a value.

\section{Theoretical Questions \uppercase\expandafter{\romannumeral7}}

If $a_0<0<b_0$ in problem \uppercase\expandafter{\romannumeral2}, the inequality will be wrong ,since $log a_0$ do not exist. 

We can get the following inequality without $a_0$:
\begin{equation}
    n\ge log_2 \frac{b_0-a_0}{\epsilon |x^*|}-1
\end{equation}
But the value of $x^*$ is unknown and if $x^*\leq 0$, the inequality is also meaningless. So, the relative error is not an appropriate measure. If we consider error$\epsilon$ which satisfy  $|x^*-y_n|\leq \epsilon$, we have inequality $n\ge \frac{log(b_0-a_0)-log\epsilon}{log2}-1$.


\end{document}
